\section{Estado da Arte}
\label{estado_da_arte}

Nesta seção serão mostrados diversas abordagens para as mais importantes etapas de um AG no que diz respeito ao PCV: Representação do cromossomo, Seleção, Cruzamento e Mutação. Além disto, serão mostradas algumas técnicas complementares ou considerações que podem ser utilizadas.

\subsection{Representação do cromossomo}
\label{representacao_do_cromossomo}

%Abordando os métodos para representação do cromossomo
As principais formas de representar o cromossomo são três: representação em matriz, inteira e notação cíclica \cite{bryant}.

Na representação em matriz é utilizada uma matriz quadrada para representar um cromossomo. A quantidade de cidades envolvidas no problema determina o tamanho desta matriz, sendo que a posição $a_{i, j}$ assume o valor \textit{um} caso a solução leve em consideração o caminho existente entre as cidades $i$ e $j$, e zero caso contrário.

Na representação inteira o cromossomo é representado por uma cadeia de inteiros: $a_1 a_2 a_3 \cdots a_n$. Isto significa que o caminho a ser percorrido parte da cidade $a_1$ para $a_2$, da cidade $a_2$ para $a_3$, e assim por diante até que da cidade $a_n$ seja retornado para a cidade $a_1$. Esta é a representação mais utilizada e é a que será considerada na explicação das demais etapas do AG.

A representação por notação cíclica é semelhante a inteira no que diz respeito a representação do cromossomo numa cadeia de inteiros, no entanto, a semântica dos valores é diferente. Na notação cíclica, a posição na cadeia representa uma cidade e o valor encontrado nesta posição indica a cidade destino. A cadeia $4312$ significa que o caminho parte da cidade $1$ para a cidade $4$, da cidade $4$ para a cidade $2$, da cidade $2$ para a $3$, retornando então para a cidade de origem $1$.

\subsection{Seleção}

%Abordando os métodos para seleção

As principais formas de seleção são três: torneio, melhor \textit{fitness}, roleta baseada no custo, roleta baseada no \textit{ranking} \cite{bhattacharyya}.

No torneio há uma disputa entre $N$ indivíduos. O melhor indivíduo (maior \textit{fitness}) tem probabilidade $p$ de vencer a disputa, o segundo melhor tem probabilidade $p * (1 - p)$, o terceiro $p * (p * (1 - p))$, e assim por diante. A quantidade de disputas realizadas depende da quantidade de indivíduos que devem ser selecionados.

Na seleção do melhor \textit{fitness}, $X\%$ dos indivíduos com melhor \textit{fitness} são escolhidos para a etapa seguinte de cruzamento, onde o valor $X$ é um parâmetro da seleção. Na roleta baseada no custo, a probabilidade de um indivíduo ser escolhido é proporcional ao valor de seu \textit{fitness} em relação aos demais. A roleta baseada no \textit{ranking} é semelhante a anterior, no entanto, a probabilidade de um indivíduo ser escolhido neste caso é proporcional a sua posição no \textit{ranking} gerado a partir do \textit{fitness}.

\subsection{Cruzamento}

%Abordando os métodos para cruzamento

As formas de realizar cruzamento investigadas foram duas: heurístico (ou guloso $1$) \cite{jog} e caminhos opostos (ou guloso $2$) \cite{bhattacharyya}.

No cruzamento heurístico a idéia consiste em escolher de forma aleatória uma cidade $C$ para iniciar e então analisar as duas cidades partindo de $C$ nos cromossomos pais, escolhendo aquela que não gera ciclo e que possui uma menor distância. Caso as duas escolhas gerem ciclos, uma das cidades que não foram escolhidas ainda é escolhida aleatoriamente e o processo continua até que todas as cidades tenham sido escolhidas. Trabalhos mostram que este método de cruzamento costuma gerar bons resultados \cite{jog}.

No cruzamento caminhos opostos, inicialmente é escolhida uma cidade $C$ como referência, localizando-a então nos dois cromossomos pais $A$ e $B$. Em seguida é iniciado o chamado movimento nos dois sentidos. No cromossomo $A$ é iniciado um movimento à esquerda partindo da cidade $C$ e no cromossomo $B$ um movimento à direita, sendo realizado um movimento por vez em cada sentido. Conforme se caminha à esquerda de $A$, a cidade encontrada é adicionada à esquerda da cidade $C$, fazendo procedimento análogo na cidade $B$. Caso a cidade já faça parte do cromossomo resultante ela é ignorada. No final deste processo, o cromossomo resultante terá a maior subsequência possível de rotas de seus pais. A idéia é que nestas etapas sejam combinadas duas subsequências, potencialmente as melhores para cada parte da rota, gerando assim uma melhor solução ao combiná-las.

\subsection{Mutação}

%Abordando os métodos para mutação

As formas de mutação investigadas foram dois\cite{bhattacharyya}: \textit{troca} gulosa e o método 2opt.

A \textit{troca} gulosa é o mecanismo mais simples de ser implementado, pois a idéia consiste apenas em fazer a troca aleatória entre duas cidades da rota, efetivando a mutação caso a rota gerada seja melhor do que a original.

O método 2opt é um pouco mais elaborado. A idéia consiste em escolher dois caminhos curtos (de uma cidade para a vizinha), trocar suas origens e destinos, e inverter uma das subsequências. Suponha o caminho completo $A B G H ... D C F E ... A$ e os dois caminhos $B G$ e $C F$. A troca consiste na remoção de $B G$ e $C F$, adição dos caminhos $B C$ e $G F$, e inversão da subsequência de $G$ para $C$. Esta troca levaria ao cromossomo $A B C D ... H G F E ... A$. Caso $(BG + CF) > (BC + GF)$, a mutação resulta num caminho menos custoso, sendo então efetivada no cromossomo original.

\subsection{Técnicas complementares}

Duas técnicas complementares foram identificadas: elitismo e cromossomos duplicados.

O elitismo consiste em manter o melhor cromossomo da geração atual na geração seguinte. Ou seja, o melhor indivíduo da geração $n$ é adicionado, sem sofrer cruzamento ou mutação, na geração $n+1$. Enquanto que cromossomos duplicados está relacionado com permitir ou não que cromossomos de mesmos genes façam parte da população.
















